{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Elements to Add to Form a Given Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minElements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构成特定和需要添加的最少元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，和两个整数 <code>limit</code> 与 <code>goal</code> 。数组 <code>nums</code> 有一条重要属性：<code>abs(nums[i]) <= limit</code> 。</p>\n",
    "\n",
    "<p>返回使数组元素总和等于 <code>goal</code> 所需要向数组中添加的 <strong>最少元素数量</strong> ，添加元素 <strong>不应改变</strong> 数组中 <code>abs(nums[i]) <= limit</code> 这一属性。</p>\n",
    "\n",
    "<p>注意，如果 <code>x >= 0</code> ，那么 <code>abs(x)</code> 等于 <code>x</code> ；否则，等于 <code>-x</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,-1,1], limit = 3, goal = -4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>可以将 -2 和 -3 添加到数组中，数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,-10,9,1], limit = 100, goal = 0\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= limit <= 10<sup>6</sup></code></li>\n",
    "\t<li><code>-limit <= nums[i] <= limit</code></li>\n",
    "\t<li><code>-10<sup>9</sup> <= goal <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-elements-to-add-to-form-a-given-sum](https://leetcode.cn/problems/minimum-elements-to-add-to-form-a-given-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-elements-to-add-to-form-a-given-sum](https://leetcode.cn/problems/minimum-elements-to-add-to-form-a-given-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,-1,1]\\n3\\n-4', '[1,-10,9,1]\\n100\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        \n",
    "        sum_nums = sum(nums)\n",
    "        di = abs(sum_nums - goal)\n",
    "        # return (di + limit - 1) // limit\n",
    "        return di//limit+(1 if di%limit else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        di = abs(sum(nums) - goal)\n",
    "        return (di + limit - 1) // limit\n",
    "        # return di//limit+(1 if di%limit else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        return ceil(abs(goal - sum(nums)) / limit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        d = abs(sum(nums) - goal)\n",
    "        return (d + limit - 1) // limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        sum_ = sum(nums)\n",
    "        if sum_ <= goal:\n",
    "            tmp = goal - sum_\n",
    "            t = tmp//limit\n",
    "            return t if tmp%limit==0 else (t+1)\n",
    "        else:\n",
    "            tmp = sum_ - goal\n",
    "            t = tmp//limit\n",
    "            return t if tmp%limit==0 else (t+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        d = abs(sum(nums) - goal)\n",
    "        return (d + limit - 1) // limit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        # 计算当前数组的总和\n",
    "        current_sum = sum(nums)\n",
    "        \n",
    "        # 计算与goal的差距\n",
    "        diff = abs(goal - current_sum)\n",
    "        \n",
    "        # 使用limit来计算需要多少步来达到goal\n",
    "        # math.ceil确保我们得到的是向上取整的数字，因为即使有一小部分差距，我们也需要添加一个元素\n",
    "        return math.ceil(diff / limit)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        cur = sum(nums)\n",
    "        diff = abs(goal-cur)\n",
    "        return (diff+limit-1)//limit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\r\n",
    "        summ = sum(nums)\r\n",
    "        abs_sum = abs(goal - summ)\r\n",
    "        return (abs_sum + limit - 1) // limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        t = sum(nums)\n",
    "        d = abs(goal - t)\n",
    "\n",
    "        return (d + limit - 1) // limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        need = abs(goal - sum(nums))\n",
    "        return (need + limit - 1) // limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        s = sum(nums)\n",
    "        delta = abs(goal - s)\n",
    "        return (delta + limit - 1) // limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        s = sum(nums)\n",
    "        if s == goal:\n",
    "            return 0\n",
    "        if s > goal:\n",
    "            return math.ceil((s-goal)/limit)\n",
    "        return math.ceil((goal-s)/limit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        s=sum(nums)\n",
    "        if goal >=0:\n",
    "            needs=abs(goal-s)\n",
    "        else:\n",
    "            needs=abs(s-goal)\n",
    "\n",
    "        if needs%limit>0:\n",
    "            return (needs//limit)+1\n",
    "        else:\n",
    "            return (needs//limit)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        mysum = 0\n",
    "        for i in nums:\n",
    "            mysum += i\n",
    "        mysum = mysum - goal\n",
    "        ans = abs(mysum) // abs(limit)\n",
    "        if(abs(mysum) % abs(limit)>0):\n",
    "            return ans + 1\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        target = goal - sum(nums)\n",
    "        return (abs(target) + limit - 1) // limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "      total = sum(nums)\n",
    "      diff = abs(goal-total)\n",
    "      return (diff-1)//limit + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        return ceil(abs(sum(nums) - goal) / limit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        if sum(nums)==goal:\n",
    "            return 0\n",
    "        c=abs(goal-sum(nums))\n",
    "        while c!=0:\n",
    "            if c//limit==0:\n",
    "                return 1\n",
    "            else:\n",
    "                return c//limit if c%limit==0 else c//limit+1\n",
    "                    \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        t=abs(sum(nums)-goal)\n",
    "        return (t+limit-1)//limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        sums = sum(nums)\n",
    "        need = goal - sums\n",
    "        if need == 0:\n",
    "            return 0\n",
    "        \n",
    "        if need < 0:\n",
    "            need = -need\n",
    "        return need//limit if need%limit == 0 else need//limit+1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums, limit, goal) -> int:\n",
    "        curr = sum(nums)\n",
    "        ans = 0\n",
    "        while curr != goal:\n",
    "            if goal > curr:\n",
    "                val = goal - curr\n",
    "                if abs(val) > limit:\n",
    "                    times=abs(val)//limit\n",
    "                    curr+=times*limit\n",
    "                    ans+=times\n",
    "                else:\n",
    "                    ans+=1\n",
    "                    curr += val\n",
    "            else:\n",
    "                val = curr - goal\n",
    "                if abs(val) > limit:\n",
    "                    times = abs(val) // limit\n",
    "                    curr -= times * limit\n",
    "                    ans += times\n",
    "                else:\n",
    "                    ans += 1\n",
    "                    curr -= val\n",
    "            \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        return math.ceil(abs(goal-sum(nums))/limit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        target = abs(goal - sum(nums))\n",
    "        return target // limit if target % limit == 0 else target // limit + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        if sum(nums)==goal:\n",
    "            return 0\n",
    "        if abs(goal-sum(nums))<=limit:\n",
    "            return 1\n",
    "        f=goal-sum(nums)\n",
    "        res=0\n",
    "        if abs(f)%limit==0:\n",
    "            return abs(f)//limit\n",
    "        else:\n",
    "            return abs(f)//limit+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        return ceil(abs(sum(nums) - goal) / limit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        return math.ceil(abs(goal - sum(nums)) / limit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        cnt = 0\n",
    "        x = goal - sum(nums)\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        elif abs(x) <= limit:\n",
    "            return 1\n",
    "        elif abs(x) > limit:\n",
    "            cnt += abs(x) // limit\n",
    "            if abs(x) % limit != 0:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        return (abs(goal - sum(nums)) + limit - 1) // limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        return (abs(sum(nums) - goal) - 1) // limit + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        delta = abs(sum(nums) - goal)\n",
    "        res = delta // limit\n",
    "        if delta % limit != 0:\n",
    "            res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        h=sum(nums)\n",
    "        q=abs(h-goal)\n",
    "        return q//limit+1 if q%limit!=0 else q//limit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        return math.ceil(abs(sum(nums) - goal) / limit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        return (abs(sum(nums) - goal) + limit - 1) // limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        #解题思路：\n",
    "        #计算出需要补全的值\n",
    "        #再根据补全值进行判断\n",
    "\n",
    "        cur_sum = sum(nums)\n",
    "        gap = abs(cur_sum - goal)\n",
    "        print(gap)\n",
    "        if gap == 0:\n",
    "            return 0\n",
    "        if gap <= limit:\n",
    "            return 1\n",
    "        else:\n",
    "            return gap // limit + 1 if gap % limit  else gap // limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        n = abs(goal - sum(nums)) / limit\n",
    "        if n % 1 == 0.0:\n",
    "            return int(n)\n",
    "        else:\n",
    "            return int(n) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minElements(self, nums: List[int], limit: int, goal: int) -> int:\n",
    "        numSum = sum(nums)\n",
    "        diff = goal - numSum\n",
    "        return (abs(diff)-1)//limit + 1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
